package codetop.microsoft.T127;

import java.util.*;

/**
 * @Author: 18362
 * @Create: 2022-08-20 14:27:11 星期六
 */
class Solution {
    private Set<String> wordSet = new HashSet<>();
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        wordSet.addAll(wordList);
        if (!wordSet.contains(endWord))
            return 0;
        return bfs(beginWord, endWord);
    }

    private int bfs(String begin, String end) {
        Queue<String> q1 = new LinkedList<>(), q2 = new LinkedList<>();
        Map<String, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
        q1.offer(begin);
        q2.offer(end);
        m1.put(begin, 0);
        m2.put(end, 0);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            int k = -1;
            if (q1.size() <= q2.size())
                k = search(q1, m1, m2);
            else
                k = search(q2, m2, m1);
            if (k >= 0)
                return k + 1;
        }
        return 0;
    }

    private int search(Queue<String> q, Map<String, Integer> cur, Map<String, Integer> other) {
        int size = q.size();
        for (int i=0; i<size; ++i) {
            String front = q.poll();
            int step = cur.get(front);
            char[] chars = front.toCharArray();
            for (int j=0; j<chars.length; j++) {
                for (int k=0; k<26; ++k) {
                    char origin = chars[j];
                    chars[j] = (char) (k + 'a');
                    String s = String.valueOf(chars);
                    if (cur.containsKey(s) || !wordSet.contains(s)) {
                        chars[j] = origin;
                        continue;
                    }
                    if (other.containsKey(s))
                        return other.get(s) + step + 1;
                    else {
                        cur.put(s, step+1);
                        q.offer(s);
                    }
                    chars[j] = origin;
                }
            }
        }
        return -1;
    }
}